package leetcode.D300.T208;

/**
 * @Author: DYZ
 * @Create: 2022-04-16 13:46:19
 */

class Trie {

    boolean end = false;
    Trie[] next = new Trie[26];

    public Trie() {
    }

    public void insert(String word) {
        insert(word, 0);
    }

    private void insert(String word, int cur) {
        if (cur == word.length()) {
            end = true;
            return;
        }
        int idx = word.charAt(cur) - 'a';
        if (next[idx] == null)
            next[idx] = new Trie();
        next[idx].insert(word, cur+1);
    }

    public boolean search(String word) {
        return find(word, 0, false);
    }

    public boolean startsWith(String prefix) {
        return find(prefix, 0, true);
    }

    private boolean find(String target, int cur, boolean prefix) {
        if (cur == target.length()) {
            if (prefix)
                return true;
            else
                return end;
        }
        Trie nextRoot = next[target.charAt(cur) - 'a'];
        if (nextRoot == null)
            return false;
        return nextRoot.find(target, cur+1, prefix);
    }
}
